import java.util.List;

public class Solution1 {
    //面试题 08.06. 汉诺塔问题
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {

        int n = A.size();
        hanotaChild(A,B,C,n);//重复子问题：将a上一堆的盘子借助b移动到c上
    }
    public void hanotaChild(List<Integer> A, List<Integer> B, List<Integer> C,int n) {
        if (n == 1) {
            C.add(A.remove(0));
            return ;
        }

        hanotaChild(A,C,B,n-1); //a借助c将上面的n-1个盘中移到b上
        C.add(A.remove(0));  //a此时只有一个盘子 直接移到c上
        hanotaChild(B,A,C,n-1); //b借助a将上面的n-1个盘子移到c上，具体实现不关心
    }
}
